Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

  • You must not modify the array (assume the array is read only).
  • You must use only constant, O(1) extra space.
  • Your runtime complexity should be less than O(n2).
  • There is only one duplicate number in the array, but it could be repeated more than once.

Solution:

  1. public class Solution {
  2.   public int findDuplicate(int[] nums) {
  3.     int a = 0, b = 0;
  5.     do {
  6.       a = nums[nums[a]];
  7.       b = nums[b];
  8.     } while (a != b);
  10.     b = 0;
  12.     while (a != b) {
  13.       a = nums[a];
  14.       b = nums[b];
  15.     }
  17.     return a;
  18.   }
  19. }